#pragma once

#include <iostream>
#include <new>
#include <vector>
#include <unordered_map>
#include <time.h>
#include <cassert>
#include <cstdbool>
#include <mutex>
#include <pthread.h>
#include <algorithm>
#include <cstring>
#include <thread>
#include <atomic>
#include <sys/mman.h>

#ifdef _WIN64
#include <windows.h>
#else
#include <unistd.h>
#endif

using std::cin;
using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; // ThreadCache最大为 256KB
static const size_t NFREELIST = 208;        // ThreadCache所需桶的个数
static const size_t NPAGES = 129;           // PageCache 所需桶的个数
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN64 // windows64 环境下
typedef unsigned long long PAGE_ID;
#elif _WIN32 // windows32 环境下
typedef size_t PAGE_ID;
#else        // 其它环境下。我使用的是Linux环境
typedef unsigned long long PAGE_ID;
#endif

// 直接去堆上按页申请空间
inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN64
    void *ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // 使用mmap分配内存
    void *ptr = mmap(nullptr, kpage << PAGE_SHIFT, PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
#endif

    if (ptr == nullptr)
        throw std::bad_alloc();

    return ptr;
}

// 直接将空间释放，还给堆
inline static void SystemFree(void *ptr, size_t size)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    int m = munmap(ptr, size);
    (void)m;
#endif
}

// ThreadCache 下的自由链表
class FreeList
{
public:
    void push(void *obj)
    {
        assert(obj);
        *(void **)obj = freelist_;
        freelist_ = obj;
        size_++;
    }

    void pushRange(void *start, void *end, size_t n)
    {
        *(void **)end = freelist_;
        freelist_ = start;

        size_ += n;
    }

    void *pop()
    {
        assert(freelist_);
        void *obj = freelist_;
        freelist_ = *(void **)freelist_;
        size_--;
        return obj;
    }

    void popRange(void *&start, void *&end, size_t n)
    {
        assert(n <= size_);
        start = freelist_;
        end = start;

        for (size_t i = 0; i < n - 1; i++)
        {
            end = *(void **)end;
        }

        freelist_ = *(void **)end;
        *(void **)end = nullptr;
        size_ -= n;
    }

    bool empty()
    {
        return freelist_ == nullptr;
    }

    size_t &maxsize()
    {
        return maxSize_;
    }

    size_t Size()
    {
        return size_;
    }

private:
    void *freelist_ = nullptr;
    size_t maxSize_ = 1; // 批量获取内存对象个数
    size_t size_ = 0;    // 自由链表长度
};

// 整体控制在最多10%左右的内碎片浪费
// [1,128]					8byte对齐	    freelist[0,16)
// [128+1,1024]				16byte对齐	    freelist[16,72)
// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
class SizeClass // ThreadCache内存对齐规则
{
public:
    // 自己实现的对齐数计算算法
    size_t MY_RoundUp_(size_t bytes, size_t alignNum)
    {
        size_t alignSize;
        if (bytes % alignNum != 0)
            alignSize = (bytes / alignNum + 1) * alignNum;
        else
            alignSize = alignNum;

        return alignSize;
    }

    // 标准对齐数计算算法
    static inline size_t RoundUp_(size_t bytes, size_t alignNum)
    {
        return ((bytes + alignNum - 1) & ~(alignNum - 1));
    }

    // 计算对齐数
    static inline size_t RoundUp(size_t size)
    {
        if (size <= 128)
            return RoundUp_(size, 8); // [1,128] : 8byte对齐
        else if (size <= 1024)
            return RoundUp_(size, 16); // [128+1,1024] : 16byte对齐
        else if (size <= 8 * 1024)
            return RoundUp_(size, 128); // [1024+1,8*1024] : 128byte对齐
        else if (size <= 64 * 1024)
            return RoundUp_(size, 1024); // [8*1024+1,64*1024]	: 1024byte对齐
        else if (size <= 256 * 1024)
            return RoundUp_(size, 8 * 1024); // [64*1024+1,256*1024] : 8*1024byte对齐
        else                                 // 大于 256kB的内存对齐
            return RoundUp_(size, 1 << PAGE_SHIFT);
    }

    // 自己实现的自由链表桶算法
    size_t My_Index_(size_t bytes, size_t alignNum)
    {
        if (bytes % alignNum == 0)
            return bytes / alignNum - 1;
        else
            return bytes / alignNum;
    }

    // 标准自由链表桶计算算法
    static inline size_t Index_(size_t bytes, size_t align_shift)
    {
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
    }

    // 计算所在桶
    static inline size_t Index(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);

        static int group[4] = {15, 56, 56, 56};
        if (bytes <= 128)
            return Index_(bytes, 3);
        else if (bytes <= 1024)
            return Index_(bytes - 128, 4) + group[0];
        else if (bytes <= 8 * 1024)
            return Index_(bytes - 1024, 7) + group[0] + group[1];
        else if (bytes <= 64 * 1024)
            return Index_(bytes - 8 * 1024, 10) + group[0] + group[1] + group[2];
        else if (bytes <= 256 * 1024)
            return Index_(bytes - 64 * 1024, 13) + group[0] + group[1] + group[2] + group[3];
        else
            assert(false);

        return -1;
    }

    // thread cache一次从中心缓存获取多少个对象
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);

        // [2, 512]，一次批量移动多少个对象的(慢启动)上限值
        // 小对象一次批量上限高
        // 大对象一次批量上限低
        int num = MAX_BYTES / size;
        if (num < 2)
            num = 2;

        // 任何大小的内存对象，最多给512个
        if (num > 512)
            num = 512;

        return num;
    }

    // 计算一次向 PageCache 获取几个页
    // 单个对象 8byte
    // ...
    // 单个对象 256KB
    static size_t NumMovePage(size_t size)
    {
        size_t num = NumMoveSize(size);
        size_t npage = num * size;

        npage >>= PAGE_SHIFT;
        if (npage == 0)
            npage = 1;

        return npage;
    }
};

// CentralCache下的, 对单个Span的结构进行描述，设计成双向链表结构
struct Span
{
    PAGE_ID pageId_ = 0; // 大块内存Span的起始页的页号
    size_t n_ = 0;       // Span拥有的页的数量

    Span *prev_ = nullptr;
    Span *next_ = nullptr;

    size_t objSize_ = 0;       // 为了释放内存时不传内存大小。记录将Span切成小对象，该类型小对象的大小
    size_t useCount_ = 0;      // 切好的小块内存，被分配给thread cache的个数
    void *freelist_ = nullptr; // 将Span切成小块内存的自由链表

    bool isUse_ = false; // 该Span是否在被CentralCache使用
};

// 将多个Span结构，用带头循环双向链表组织起来
class SpanList
{
public:
    SpanList()
    {
        head_ = new Span;
        head_->next_ = head_;
        head_->prev_ = head_;
    }

    void Insert(Span *pos, Span *newspan)
    {
        assert(pos);
        assert(newspan);

        Span *prev = pos->prev_;
        // prev  newspan  pos
        newspan->next_ = pos;
        pos->prev_ = newspan;
        prev->next_ = newspan;
        newspan->prev_ = prev;
    }

    void Erase(Span *pos)
    {
        assert(pos);
        assert(pos != head_);

        pos->prev_->next_ = pos->next_;
        pos->next_->prev_ = pos->prev_;

        /* Span *prev = pos->prev_;
        Span *next = pos->next_;
        prev->next_ = next;
        next->prev_ = prev; */
    }

    Span *Begin()
    {
        return head_->next_;
    }

    Span *End()
    {
        return head_;
    }

    void PushFront(Span *span)
    {
        Insert(Begin(), span);
    }

    bool Empty()
    {
        return head_->next_ = head_;
    }

    Span *PopFront()
    {
        Span *front = head_->next_;
        Erase(front);
        return front;
    }

private:
    Span *head_; // 哨兵头节点

public:
    std::mutex mtx_; // 桶锁
};